Cryptographic systems are concerned with confidentiality, authenticity, integrity, and non-repudiation of data sent from a first party to a second party. Modern cryptographic schemes based on the discrete logarithm problem in a finite abelian group are designed to address these concerns. One such finite abelian group is a group of points on an elliptic curve (EC) over a finite field with group operation provided by simple algebraic formulae. Such a group is becoming increasingly utilized in cryptographic systems because corresponding group operations are relatively simple to realize in hardware or software.
To fully realize implementation efficiencies using elliptic curve groups, associated field arithmetic should be carefully considered. For instance, field inversions may be significantly more processing intensive to implement as compared to multiplication operations. In such a scenario, weighted projective coordinates are typically utilized so that point addition can be performed using field multiplications, as described by Blake et al, “Elliptic Curves in Cryptography”, Cambridge University Press, 1999, pages 59-60, thereby deferring field inversions, for example, until the end of a long sequence of multiplications. However, the computational cost of substantially eliminating inversions is that an increased number of multiplications are calculated. An efficient technique to multiply two elements in a finite group G is essential to performing efficient exponentiation.
Exponentiation is commonly used in public-key cryptography to calculate a scalar multiple n of points P on an elliptic curve, where n is a very large integer (e.g., a random number or private key), and wherein P is a weighted projective coordinate. An unsophisticated way to compute nP is to do n−1 operations in the group G. For cryptographic applications, the order of the group G typically exceeds 2160 elements, and may exceed 22024 elements. Such operations are computationally intensive, and most choices of n are large enough that it becomes substantially infeasible, from the point of view of providing a responsive application, to calculate nP using n−1 successive multiplications by P. However, there are a number of techniques that can be used to reduce the computational costs of exponentiation.
For instance, repeated square-and-multiply algorithms (i.e., binary exponentiation) and windowing methods such as described by Blake et al, “Elliptic Curves in Cryptography”, Cambridge University Press, 1999, pages 63-72, can reduce the computational costs of exponentiation. More particularly, repeated square-and-multiply algorithms divide the exponent n into smaller sums of powers of two (2), which respectively take less processing resources to compute. For instance, given a projective point P with coordinates (x, y, z) on an elliptic curve over a finite field, n can be divided into pieces of size 23 (i.e., using a window of size 3) to calculate scalar multiples of P (23P, or 8P) with multiple point doubling iterations. To accomplish this, existing systems typically input P=(x, y, z) into the square-and-multiply algorithm to generate 2P. Next, the coordinates for 2P (output from the first doubling operation) are input as (x, y, z) into the same square-and-multiply algorithm to obtain 4P. Finally, this iterative process is repeated one more time to input the coordinates for 4P (output from the second doubling operation) as (x, y, z) into the same square-and-multiply algorithm to obtain 8P. The repeated doubling method to obtain 8P involves a total of 30 field multiplications.